package class01


// 括号有效配对
// 返回一个括号字符串中，最长有效子串的长度

func MyMaxSubValidLen(s string) int {
	dp := make([]int, len(s))
	var ans int
	for i:=1; i<len(s); i++ {
		if s[i] == '(' {
			dp[i] = 0
		} else {
			if dp[i-1] == 0 {
				if s[i-1] == '('{
					dp[i] = 2
				}
			} else {
				if s[i-1-dp[i-1]] == '(' {
					if i-2-dp[i-1] >= 0 {
						dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]]
					} else {
						dp[i] = dp[i-1] + 2
					}
				}
			}
		}
		ans = max(ans, dp[i])
	}
	return ans
}

func MaxSubValidLen(s string) int {
	if len(s) < 2 {
		return 0
	}
	dp := make([]int, len(s))
	var ans int
	var pre int
	for i:=1; i<len(s); i++ {
		if s[i] == ')' {
			pre = i - dp[i-1] - 1
			if pre >= 0 && dp[pre] == '(' {
				dp[i] = dp[i-1] + 2
				if pre > 0 {
					dp[i] += dp[pre-1]
				}
			}
		}
	}
	return ans
}